package org.hot100_5.leetcode215;

public class Solution {


    public int findKthLargest(int[] nums, int k) {
        quickSort(nums,0, nums.length-1);
        return nums[nums.length-k];
    }

    private void quickSort(int[] nums, int start, int end) {
        if (start >= end) {
            return;
        }
        int piv = nums[start];
        int left = start;
        int right = end;
        int curr = start + 1;

        while (curr <= right) {
            if (nums[curr] < piv) {
                swap(nums, curr, left);
                curr++;
                left++;
            } else if (nums[curr] > piv) {
                swap(nums, curr, right);
                right--;
            } else {
                curr++;
            }
        }

        quickSort(nums, start, left - 1);
        quickSort(nums, right + 1, end);
    }

    private void swap(int[] nums, int index1, int index2) {
        if (index1 == index2) {
            return;
        }
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }


}
